import { PathType } from "./clipper";
import { Vec2 } from "./geometry";
import { Vertex } from "./vertex";
import { Mathf } from "./mathf";
import { fgCanvas } from "@clipper/ui";
import { LocalMin } from "./localmin";

export class ActiveEdge {
  type: PathType;
  bottom: Vertex;
  top: Vertex;
  dx: number = 0;
  win_dx: number = 0; // 向上：1 向下: -1
  win_cnt: number = 0;
  slope: number = 0;
  localMin: LocalMin;

  // ael links
  next_in_ael?: ActiveEdge;
  prev_in_ael?: ActiveEdge;
  // sel links
  next_in_sel?: ActiveEdge;
  prev_in_sel?: ActiveEdge;
  jump_in_sel?: ActiveEdge;

  get center() {
    return this.bottom.point.add(this.top.point).div(2);
  }

  get horizLeft() {
    return this.slope === Infinity;
  }

  get horizRight() {
    return this.slope === -Infinity;
  }

  get nextVertex(): Vertex | undefined {
    return this.win_dx < 0 ? this.top.prev : this.top.next;
  }

  static compare(edge1: ActiveEdge, edge2: ActiveEdge) {
    if (edge1.dx !== edge2.dx) {
      return edge1.dx < edge2.dx ? -1 : 1;
    }

    if (edge1.slope !== edge2.slope) {
      return edge1.slope > edge2.slope ? -1 : 1;
    }

    return 0;
  }

  constructor(type: PathType, bottom: Vertex, top: Vertex, localMin: LocalMin) {
    this.type = type;
    this.bottom = bottom;
    this.top = top;
    this.localMin = localMin;
    this.dx = this.bottom.x;
    this.updateSlope();
  }

  updateSlope() {
    let ydiff = this.top.y - this.bottom.y;
    let xdiff = this.top.x - this.bottom.x;
    if (ydiff === 0) {
      this.slope = xdiff > 0 ? -Infinity : Infinity;
    } else {
      this.slope = xdiff / ydiff;
    }
  }

  updateDX(y: number) {
    if (y > this.bottom.y || y < this.top.y) {
      throw `y coord overflow, y ${y} bottom ${this.bottom.y} top ${this.top.y}`;
    }

    let dy = y - this.bottom.y;
    let ydiff = this.top.y - this.bottom.y;
    if (Mathf.isZero(ydiff)) {
      throw `horizontal edge`;
    }

    let t = dy / ydiff;
    this.dx = this.bottom.x * (1 - t) + this.top.x * t;
  }
}

export class AEL {
  aelRoot?: ActiveEdge;
  selRoot?: ActiveEdge;

  reset() {
    this.aelRoot = undefined;
    this.selRoot = undefined;
  }

  insert(edge: ActiveEdge) {
    if (!this.aelRoot) {
      this.aelRoot = edge;
    } else if (ActiveEdge.compare(edge, this.aelRoot) < 0) {
      edge.next_in_ael = this.aelRoot;
      this.aelRoot.prev_in_ael = edge;
      this.aelRoot = edge;
    } else {
      let e: ActiveEdge = this.aelRoot;
      while (e.next_in_ael && ActiveEdge.compare(e.next_in_ael, edge) <= 0) {
        e = e.next_in_ael;
      }
      let next = e.next_in_ael;
      e.next_in_ael = edge;
      edge.next_in_ael = next;
      edge.prev_in_ael = e;
      if (next) {
        next.prev_in_ael = edge;
      }
    }
  }

  insertAfterInAEL(dst: ActiveEdge, src: ActiveEdge) {
    let next = src.next_in_ael;
    src.next_in_ael = dst;
    dst.next_in_ael = next;
    dst.prev_in_ael = src;
    if (next) {
      next.prev_in_ael = dst;
    }
  }

  removeEdge(edge: ActiveEdge) {
    this.removeInAEL(edge);
    this.removeInSEL(edge);
  }

  removeInAEL(edge: ActiveEdge) {
    let prev = edge.prev_in_ael;
    let next = edge.next_in_ael;

    // 处理edge2
    if (prev) {
      prev.next_in_ael = next;
    } else {
      this.aelRoot = next;
    }

    if (next) {
      next.prev_in_ael = prev;
    }
  }

  swapInAEL(edge1: ActiveEdge, edge2: ActiveEdge) {
    let prev1 = edge1.prev_in_ael;
    let next1 = edge1.next_in_ael;
    let prev2 = edge2.prev_in_ael;
    let next2 = edge2.next_in_ael;

    // 处理edge2
    if (prev1 !== edge2) {
      if (prev1) {
        prev1.next_in_ael = edge2;
      } else {
        this.aelRoot = edge2;
      }
      edge2.prev_in_ael = prev1;

      edge1.next_in_ael = next2;
      if (next2) {
        next2.prev_in_ael = edge1;
      }
    } else {
      edge1.next_in_ael = edge2;
      edge2.prev_in_ael = edge1;
    }

    // 处理edge1
    if (prev2 !== edge1) {
      if (prev2) {
        prev2.next_in_ael = edge1;
      } else {
        this.aelRoot = edge1;
      }
      edge1.prev_in_ael = prev2;

      edge2.next_in_ael = next1;
      if (next1) {
        next1.prev_in_ael = edge2;
      }
    } else {
      edge2.next_in_ael = edge1;
      edge1.prev_in_ael = edge2;
    }
  }

  removeInSEL(edge: ActiveEdge) {
    let prev = edge.prev_in_sel;
    let next = edge.next_in_sel;

    // 处理edge2
    if (prev) {
      prev.next_in_sel = next;
    } else {
      this.selRoot = next;
    }

    if (next) {
      next.prev_in_sel = prev;
    }
  }

  insertBeforeInSEL(edge: ActiveEdge, targetEdge: ActiveEdge) {
    let prev = targetEdge.prev_in_sel;

    if (prev) {
      prev.next_in_sel = edge;
    } else {
      this.selRoot = edge;
    }
    edge.prev_in_sel = prev;
    edge.next_in_sel = targetEdge;
    targetEdge.prev_in_sel = edge;
  }

  /**
   * 链表归并排序计算交点
   * @date 2023/9/11 - 15:27:47
   *
   * @param {number} y
   */
  buildIntersections(y: number) {
    let ints: Intersection[] = [];
    this.updateDXAndCopyToSEL(y);

    let left = this.selRoot;
    while (left && left.jump_in_sel) {
      let lastHead: ActiveEdge | undefined;
      while (left && left.jump_in_sel) {
        let head: ActiveEdge = left;
        let lend: ActiveEdge | undefined = left.jump_in_sel;
        let right: ActiveEdge = lend;
        let rend: ActiveEdge | undefined = right.jump_in_sel;

        while (left !== lend && right !== rend) {
          fgCanvas.clear();
          fgCanvas.drawScanLine(y);
          fgCanvas.labelOnEdge(left!, Math.max(y, left!.center.y), "left");
          fgCanvas.labelOnEdge(right!, Math.max(y, right!.center.y), "right");
          let edge = this.selRoot,
            count = 0;
          while (edge) {
            fgCanvas.labelOnEdge(edge, y, `${++count}`);
            edge = edge.next_in_sel;
          }
          if (ActiveEdge.compare(right, left!) < 0) {
            lend = right.next_in_sel;
            if (left === head) {
              head = right;
            }
            this.calculateIntsInSEL(left!, right, y, ints);
            this.removeInSEL(right);
            this.insertBeforeInSEL(right, left!);
            right = lend!;
          } else {
            left = left!.next_in_sel;
          }
        }
        head.jump_in_sel = rend;
        left = rend;
        if (lastHead) {
          lastHead.jump_in_sel = head;
        }
        lastHead = head;
      }
      left = this.selRoot;
    }

    return ints;
  }

  updateDXAndCopyToSEL(y: number) {
    this.selRoot = this.aelRoot;
    let e = this.aelRoot;
    while (e) {
      e.updateDX(y);
      e.prev_in_sel = e.prev_in_ael;
      e.next_in_sel = e.next_in_ael;
      e.jump_in_sel = e.next_in_ael;
      e = e.next_in_ael;
    }
  }

  calculateIntsInSEL(
    from: ActiveEdge,
    to: ActiveEdge,
    y: number,
    intss: Intersection[]
  ) {
    let edge = from;
    while (edge !== to) {
      let ints = this.doIntersection(edge, to, y);
      if (!ints) {
        throw `unexpected error: no intersection detected!!!`;
      }
      intss.push(ints);
      edge = edge.next_in_sel!;
    }
  }

  doIntersection(edge1: ActiveEdge, edge2: ActiveEdge, y: number) {
    let p1 = edge1.bottom.point;
    let p2 = edge1.top.point;
    let p3 = edge2.bottom.point;
    let p4 = edge2.top.point;

    // 跨立测试1
    let s1 = p2.sub(p1);
    let v1 = p3.sub(p1);
    let v2 = p4.sub(p1);
    let a1 = s1.cross(v1);
    let a2 = s1.cross(v2);
    if (Mathf.bigThan(a1 * a2, 0)) {
      return undefined;
    }

    // 跨立测试2
    let s2 = p4.sub(p3);
    let v3 = p1.sub(p3);
    let v4 = p2.sub(p3);
    let a3 = s2.cross(v3);
    let a4 = s2.cross(v4);
    if (Mathf.bigThan(a3 * a4, 0)) {
      return undefined;
    }

    // 共线测试
    let a5 = s2.cross(s1);

    let t: number;
    if (Mathf.isZero(a5)) {
      t = (y - p3.y) / (p4.y - p3.y); // 水平共线怎么办?
    } else {
      t = Math.abs(a1) / (Math.abs(a1) + Math.abs(a2));
    }

    return new Intersection(edge1, edge2, Vec2.lerp(t, p3, p4));
  }
}

export class Intersection {
  point: Vec2;
  edge1: ActiveEdge;
  edge2: ActiveEdge;

  static compare(ints1: Intersection, ints2: Intersection) {
    if (ints1.point.y !== ints2.point.y) {
      return ints1.point.y > ints2.point.y ? -1 : 1;
    }

    if (ints1.point.x !== ints2.point.x) {
      return ints1.point.x < ints2.point.x ? -1 : 1;
    }

    return 0;
  }

  constructor(edge1: ActiveEdge, edge2: ActiveEdge, point: Vec2) {
    this.edge1 = edge1;
    this.edge2 = edge2;
    this.point = point;
  }
}
